#ifndef ALGO_RBTREE_H
#define ALGO_RBTREE_H

#include "Map.h"
#include "Pair.h"
#include <map>

namespace algo {
  template <typename K, typename V>
  class RBTree : public Map<K, V> {
  private:
    typedef typename std::map<K, V>::const_iterator Iter;

  public:
    virtual void insert(K key, V value) {
      map[key] = value;
    }

    virtual V deleteKey(K key) {
      V v = map[key];
      map.erase(key);
      return v;
    }

    virtual V deleteMinimum() {
      V v = map.begin()->second;
      map.erase(map.begin());
      return v;
    }

    virtual V lookup(K key) const {
      return map.find(key)->second;
    }

    virtual Pair<K, V> findNext(K key) const {
      Pair<K, V> k;
      std::pair<Iter, Iter> pair = map.equal_range(key);
      if (pair.first->first >= key) {
        k.l = pair.first->first;
        k.r = pair.first->second;
        return k;
      }
      k.l = pair.second->first;
      k.r = pair.second->second;
      return k;
    }

    virtual Pair<K, V> findMin() const {
      Iter it = map.begin();
      return Pair<K, V>(it->first, it->second);
    }

  private:
    std::map<K, V> map;
  };
}

#endif // ALGO_RBTREE_H
